import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class SubrectangleQueries {
    public int[][] arr;
    public SubrectangleQueries(int[][] rectangle) {
        arr=new int[rectangle.length][rectangle[0].length];
        for(int i=0;i<arr.length;i++){
            arr[i]=rectangle[i].clone();
        }
    }

    public void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        for(int i=row1;i<=row2;i++){
            for(int j=col1;j<=col2;j++){
                arr[i][j]=newValue;
            }
        }
    }

    public int getValue(int row, int col) {
        return arr[row][col];
    }
}










public class project {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        for(int i=0;i<nums.length;i++){
            for(int j=0;j<nums.length;j++){
                if(i!=j){
                    if(Math.abs(nums[i]-nums[j])<=t&&Math.abs(i-j)<=k){
                        return true;
                    }
                }
            }
        }
        return false;
    }















    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> list=new ArrayList<>();
        Queue<TreeNode> queue=new ArrayDeque<>();
        boolean bool=true;
        if(root!=null){
            queue.add(root);
            while(!queue.isEmpty()){
                int size=queue.size();
                Deque<Integer> deque=new ArrayDeque<>();
                for(int i=0;i<size;i++){
                    TreeNode tmp=queue.poll();
                    if(bool){
                        deque.addLast(tmp.val);
                    }else{
                        deque.addFirst(tmp.val);
                    }
                    if(tmp.left!=null){
                        queue.add(tmp.left);
                    }
                    if(tmp.right!=null){
                        queue.add(tmp.right);
                    }
                }
                list.add(new ArrayList<>(deque));
                bool=!bool;
            }
        }
        return list;
    }














    public int findDuplicate(int[] nums) {
        int left=0;
        int right=0;
        do{
            left=nums[left];
            right=nums[nums[right]];
        }while(left!=right);
        left=0;
        while(left!=right ){
            left=nums[left];
            right=nums[right];
        }
        return left;
    }















    public boolean isAlienSorted(String[] words, String order) {
        Map<Character,Integer> map=new HashMap<>();
        for(int i=0;i<order.length();i++){
            map.put(order.charAt(i),i);
        }
        for(int i=1;i<words.length;i++){
            String str1=words[i-1];
            String str2=words[i];
            int len1=str1.length();
            int len2=str2.length();
            boolean bool=false;
            for(int j=0;j<Math.min(len1,len2);j++){
                if(str1.charAt(j)!=str2.charAt(j)){
                    if(map.get(str1.charAt(j))>map.get(str2.charAt(j))){
                        return false;
                    }
                    bool=true;
                    break;
                }
            }
            if(!bool){
                if(len1>len2){
                    return false;
                }
            }
        }
        return true;
    }














    public int distanceBetweenBusStops(int[] distance, int start, int destination) {
        int s=0;
        int d=0;
        int len=distance.length;
        for(int i=start;i!=destination;i=(i+1)%len){
            s+=distance[i];
        }
        for(int i=destination;i!=start;i=(i+1)%len){
            d+=distance[i];
            if(d>=s){
                return s;
            }
        }
        return d;
    }
















    public int timeRequiredToBuy(int[] tickets, int k) {
        int len=tickets.length;
        int index=0;
        int count=0;
        while(tickets[k]!=0){
            if(tickets[index]>0){
                tickets[index]--;
                count++;
            }
            index++;
            if(index==len){
                index=0;
            }
        }
        return count;
    }













    public int projectionArea(int[][] grid) {
        int len=grid.length;
        int ret=0;
        for(int i=0;i<len;i++){
            int row=0;
            int col=0;
            for(int j=0;j<len;j++){
                if(grid[i][j]>0){
                    ret++;
                }
                row=Math.max(row,grid[i][j]);
                col=Math.max(col,grid[j][i]);
            }
            ret+=row+col;
        }
        return ret;
    }











    public int surfaceArea(int[][] grid) {
        int ret=0;
        int len=grid.length;
        for(int i=0;i<len;i++){
            for(int j=0;j<len;j++){
                int tmp=grid[i][j];
                if(tmp>0){
                    ret+=(tmp<<2)+2;
                    ret-=i>0?Math.min(tmp,grid[i-1][j])<<1:0;
                    ret-=j>0?Math.min(tmp,grid[i][j-1])<<1:0;
                }
            }
        }
        return ret;
    }














    public boolean hasGroupsSizeX(int[] deck) {
        int[] arr=new int[100000];
        for(int i : deck){
            arr[i]++;
        }
        int tmp=arr[deck[0]];
        for(int i : arr){
            if(i!=0){
                tmp=gcd(tmp,i);
                if(tmp<2){
                    return false;
                }
            }
        }
        return true;
    }
    public int gcd(int a,int b){
        return a%b==0?b:gcd(b,a%b);
    }












    public String[] reorderLogFiles(String[] logs) {
        Arrays.sort(logs,(logs1,logs2)->{
            String[] str1=logs1.split(" ",2);
            String[] str2=logs2.split(" ",2);
            boolean bool1=Character.isDigit(str1[1].charAt(0));
            boolean bool2=Character.isDigit(str2[1].charAt(0));
            if(!bool1&&!bool2){
                int tmp=str1[1].compareTo(str2[1]);
                if(tmp!=0){
                    return tmp;
                }
                return str1[0].compareTo(str2[0]);
            }
            return bool1?(bool2?0:1):-1;
        });
        return logs;
    }
}
